#include "tree.h"
#include <iostream>
#include <unordered_map>
#include <vector>

int BinaryTree::create_binary_tree_by_array(const std::vector<int> &init_array)
{
    if (init_array.empty()) {
        std::cout << "Error! init_array is empty" << std::endl;
        return -1;
    }

    /* 通过下标找节点，如果结点已经分配过了则不需要再分配了 */
    /* 比如通过层序遍历到一个节点的父节点的时候，由于需要构建树，因此父节点会创建子节点，后续就不需要再继续创建
     */
    unordered_map<int, TreeNode *> index_to_node;
    decltype(init_array.size()) size = init_array.size();

    for (auto i = 0; i < size; ++i) {
        /* 使用数组创建二叉树的时候，INT_MAX表示null */
        if (init_array[i] == INT_MAX) {
            continue;
        }

        /* 找到当前节点，则并不需要new一个新的对象了 */
        if (index_to_node.find(i) == index_to_node.end()) {
            index_to_node[i] = new TreeNode(init_array[i]);
        }

        /* 查看子节点是否为空，子节点不为空则new一个新对象，用来存子节点 */
        /* new完的新子节点对象，需要存到map里面 */
        if ((i * 2 + 1) < size && init_array[i * 2 + 1] != INT_MAX) {
            index_to_node[i]->left = index_to_node[i * 2 + 1] = new TreeNode(init_array[i * 2 + 1]);
        }

        /* 查看子节点是否为空，子节点不为空则new一个新对象，用来存子节点 */
        /* new完的新子节点对象，需要存到map里面 */
        if ((i * 2 + 2) < size && init_array[i * 2 + 2] != INT_MAX) {
            index_to_node[i]->right = index_to_node[i * 2 + 2] = new TreeNode(init_array[i * 2 + 2]);
        }
    }
    this->set_root(index_to_node[0]);
    std::cout << "Sucess to create binary tree!" << std::endl;
    return 0;
}

/* 这种构建方法是一种分治的思想 */
/*
 * 参数说明：
 * 1. start_pre 表示根节点在前序序列中的下标
 * 2. start_pre 和 end_pre 表示当前子树在中序序列中的起始下标
 */
TreeNode *BinaryTree::create_tree_by_preorder_inorder_help(const std::vector<int> &preorder, const std::vector<int> &inorder, int start_pre, int end_pre, int start_in, int end_in,
                                                           const std::unordered_map<int, int> &value_2_index)
{
    if (start_pre > end_pre) {
        return nullptr;
    }

    int root_value = preorder[start_pre];
    TreeNode *sub_tree_root = new TreeNode(root_value);

    int root_index = value_2_index.at(root_value);
    int left_sub_tree_size = root_index - start_in;

    sub_tree_root->left = create_tree_by_preorder_inorder_help(preorder, inorder, start_pre + 1, start_pre + left_sub_tree_size, start_in, root_index - 1, value_2_index);

    sub_tree_root->right = create_tree_by_preorder_inorder_help(preorder, inorder, start_pre + left_sub_tree_size + 1, end_pre, root_index + 1, end_in, value_2_index);

    return sub_tree_root;
}

TreeNode *BinaryTree::create_binary_tree_preorder_inorder(const std::vector<int> &preorder, const std::vector<int> &inorder)
{
    std::unordered_map<int, int> val_to_index;
    int size = inorder.size();

    for (int index = 0; index < size; ++index) {
        val_to_index[inorder[index]] = index;
    }

    this->root = create_tree_by_preorder_inorder_help(preorder, inorder, 0, size - 1, 0, size - 1, val_to_index);

    return this->root;
}

/* 这种构建方法是一种分治的思想 */
/*
 * 参数说明：
 * 1. end_last 表示根节点在前序序列中的下标
 * 2. start_in 和 end_in 表示当前子树在中序序列中的起始下标
 */
TreeNode *BinaryTree::create_tree_by_inorder_lastorder_help(const std::vector<int> &inorder, const std::vector<int> &lastorder, int start_in, int end_in, int start_last, int end_last,
                                                            const std::unordered_map<int, int> &value_2_index)
{
    if (start_in > end_in) {
        return nullptr;
    }
    int sub_tree_root_value = lastorder[end_last];
    TreeNode *sub_tree_root = new TreeNode(sub_tree_root_value);

    int tree_index_in_inorder = value_2_index.at(sub_tree_root_value);
    int left_sub_tree_size = tree_index_in_inorder - start_in;

    std::cout << "创建节点：" << sub_tree_root_value << " " << std::endl;
    sub_tree_root->left = create_tree_by_inorder_lastorder_help(inorder, lastorder, start_in, tree_index_in_inorder - 1, start_last, start_last + left_sub_tree_size - 1, value_2_index);

    sub_tree_root->right = create_tree_by_inorder_lastorder_help(inorder, lastorder, tree_index_in_inorder + 1, end_in, start_last + left_sub_tree_size, end_last - 1, value_2_index);

    return sub_tree_root;
}

TreeNode *BinaryTree::create_binary_tree_inorder_lastorder(const std::vector<int> &inorder, const std::vector<int> &lastorder)
{
    std::unordered_map<int, int> value_2_index;
    int size = inorder.size();

    for (int index = 0; index < size; ++index) {
        value_2_index[inorder[index]] = index;
    }

    this->root = create_tree_by_inorder_lastorder_help(inorder, lastorder, 0, size - 1, 0, size - 1, value_2_index);
    return this->root;
}

void BinaryTree::level_order()
{
    if (this->root == nullptr) {
        std::cout << "Binary tree is empty, just return" << std::endl;
    }
    std::cout << "Binary tree level order: ";
    std::queue<TreeNode *> tree_queue;
    tree_queue.push(this->root);

    while (!tree_queue.empty()) {
        TreeNode *node = tree_queue.front();
        if (node->value != INT_MAX) {
            std::cout << node->value << " ";
        }
        tree_queue.pop();
        if (node->left != nullptr) {
            tree_queue.push(node->left);
        }
        if (node->right != nullptr) {
            tree_queue.push(node->right);
        }
    }
}

void BinaryTree::pre_order(TreeNode *root)
{
    if (root == nullptr) {
        return;
    }

    if (root == this->root) {
        std::cout << "Binary pre order: ";
    }

    std::cout << root->value << " ";
    // if (root->left == nullptr) {
    //     std::cout << root->value << "的左孩子为空 ";
    // }
    // if (root->right == nullptr) {
    //     std::cout << root->value << "的右孩子为空 ";
    // }
    pre_order(root->left);
    pre_order(root->right);
}

void BinaryTree::in_order(TreeNode *root)
{
    if (root == nullptr) {
        return;
    }

    if (root == this->root) {
        std::cout << "Binary mid order: ";
    }

    in_order(root->left);
    std::cout << root->value << " ";
    in_order(root->right);
}

void BinaryTree::last_order(TreeNode *root)
{
    if (root == nullptr) {
        return;
    }

    if (root == this->root) {
        std::cout << "Binary last order: ";
    }

    last_order(root->left);
    last_order(root->right);
    std::cout << root->value << " ";
}

TreeNode *BinarySearchTree::search_node(int val)
{
    if (this->root == nullptr) {
        return nullptr;
    }

    TreeNode *tmp = this->root;
    int tmp_value = 0;

    while (tmp) {
        tmp_value = tmp->value;
        if (tmp_value == val) {
            return tmp;
        } else if (tmp_value > val) {
            tmp = tmp->left;
        } else {
            tmp = tmp->right;
        }
    }

    return nullptr;
}

void BinarySearchTree::insert_node(int val)
{
    if (this->root == nullptr) {
        root = new TreeNode(val);
        return;
    }

    TreeNode *cur_node = root;
    TreeNode *pre = root;
    int cur_val = 0;

    while (cur_node) {
        cur_val = cur_node->value;
        pre = cur_node;
        /* If value of insert_node is equal to cur_node's, just return. */
        if (cur_val == val) {
            return;
        } else {
            cur_node = (cur_val > val) ? cur_node->left : cur_node->right;
        }
    }

    if (val > pre->value) {
        pre->right = (new TreeNode(val));
    } else {
        pre->left = (new TreeNode(val));
    }
}

void BinarySearchTree::delete_node(int val)
{
#if 1
    // 如果为空，直接返回
    if (this->root == nullptr) {
        return;
    }

    TreeNode *cur_node = this->root;
    TreeNode *pre_node = nullptr;

    while (cur_node) {
        // 找到了待删除节点，break
        if (cur_node->value == val) {
            break;
        }
        // 这一行不能提到while最前面，因为如果找到了某个节点的话，pre_node就和要删除的节点指向同一个节点了，就会有问题
        pre_node = cur_node;
        if (val > cur_node->value) {
            cur_node = cur_node->right;
        } else if (val < cur_node->value) {
            cur_node = cur_node->left;
        }
    }

    if (cur_node == nullptr) {
        return;
    }

    // 如果有一边的子树为空，则将当前节点替换为其子树的根节点即可，因为子树也是一棵搜索树
    if (cur_node->left == nullptr || cur_node->right == nullptr) {
        TreeNode *child_node = cur_node->left ? cur_node->left : cur_node->right;
        if (cur_node != root) {
            if (cur_node == pre_node->left) {
                pre_node->left = child_node;
            } else if (cur_node == pre_node->right) {
                pre_node->right = child_node;
            }
        } else {
            // 删除的是根节点，重新指定根节点
            this->root = child_node;
        }
        std::cout << "Delete node: " << val << std::endl;
        delete cur_node;
    } else {
        // 节点的度为2，找右子树中最大的节点，将当前节点的值替换成右子树最小结点的值，并递归删除右子树的最小节点
        TreeNode *tmp = cur_node->right;

        // 遍历找到ttmp的左子树最小的节点
        while (tmp->left) {
            tmp = tmp->left;
        }

        int tmp_val = tmp->value;
        // std::cout << "Recurse delete node: " << val << std::endl;
        //  递归删除节点右子树中最小的节点
        delete_node(tmp_val);
        // 将当前节点的值替换为右子树中最小的节点
        cur_node->value = tmp_val;
    }
#endif

#if 0
    // 若树为空，直接提前返回
    if (root == nullptr)
        return;
    TreeNode *cur = root, *pre = nullptr;
    // 循环查找，越过叶节点后跳出
    while (cur != nullptr) {
        // 找到待删除节点，跳出循环
        if (cur->value == num)
            break;
        pre = cur;
        // 待删除节点在 cur 的右子树中
        if (cur->value < num)
            cur = cur->right;
        // 待删除节点在 cur 的左子树中
        else
            cur = cur->left;
    }
    // 若无待删除节点，则直接返回
    if (cur == nullptr)
        return;
    if (pre == nullptr) {
        std::cout << "pre为空" << std::endl;
    }
    // 子节点数量 = 0 or 1
    if (cur->left == nullptr || cur->right == nullptr) {
        // 当子节点数量 = 0 / 1 时， child = nullptr / 该子节点
        TreeNode *child = cur->left != nullptr ? cur->left : cur->right;
        // 删除节点 cur
        if (cur != root) {
            if (pre->left == cur)
                pre->left = child;
            else
                pre->right = child;
        } else {
            // 若删除节点为根节点，则重新指定根节点
            root = child;
        }
        // 释放内存
        delete cur;
    }
    // 子节点数量 = 2
    else {
        // 获取中序遍历中 cur 的下一个节点
        TreeNode *tmp = cur->right;
        while (tmp->left != nullptr) {
            tmp = tmp->left;
        }
        int tmpvalue = tmp->value;
        // 递归删除节点 tmp
        delete_node(tmp->value);
        // 用 tmp 覆盖 cur
        cur->value = tmpvalue;
    }
#endif
}

BinaryTree::~BinaryTree()
{
    std::cout << "Call ~BinaryTree" << std::endl;
#if 1
    if (this->root == nullptr) {
        std::cout << "Binary tree is empty, just return" << std::endl;
    }
    std::cout << "BinaryTree tree distruct " << std::endl;
    std::queue<TreeNode *> tree_queue;
    tree_queue.push(root);
    while (!tree_queue.empty()) {
        TreeNode *front_node = tree_queue.front();
        tree_queue.pop();

        if (front_node == nullptr) {
            continue;
        }

        if (front_node->left != nullptr) {
            tree_queue.push(front_node->left);
        }

        if (front_node->right != nullptr) {
            tree_queue.push(front_node->right);
        }

        std::cout << "开始释放节点：" << front_node->value << " " << std::endl;
        delete front_node;
    }
#endif
}

BinaryTree::BinaryTree(const std::vector<int> &order1, const std::vector<int> order2, int method)
{
    switch (method) {
    case 1:
        std::cout << "Start to create binary tree by preorder and inorder" << std::endl;
        if (create_binary_tree_preorder_inorder(order1, order2)) {
            std::cout << "Success to create binary tree by preorder and inorder" << std::endl;
        } else {
            std::cout << "Fail to create binary tree by preorder and inorder" << std::endl;
        }
        break;
    case 2:
        std::cout << "Start to create binary tree by inorder and lastorder" << std::endl;
        if (create_binary_tree_inorder_lastorder(order1, order2)) {
            std::cout << "Success to create binary tree by inorder and lastorder" << std::endl;
        } else {
            std::cout << "Fail to create binary tree by inorder and lastorder" << std::endl;
        }
        break;
    default:
        break;
    }
}

BinarySearchTree::BinarySearchTree(const std::vector<int> &order1, const std::vector<int> order2, int method)
{
    this->set_root(nullptr);
    switch (method) {
    case 1:
        std::cout << "Start to create binary tree by preorder and inorder" << std::endl;
        if (create_binary_tree_preorder_inorder(order1, order2)) {
            std::cout << "Success to create binary tree by preorder and inorder" << std::endl;
        } else {
            std::cout << "Fail to create binary tree by preorder and inorder" << std::endl;
        }
        break;
    case 2:
        std::cout << "Start to create binary tree by inorder and lastorder" << std::endl;
        if (create_binary_tree_inorder_lastorder(order1, order2)) {
            std::cout << "Success to create binary tree by inorder and lastorder" << std::endl;
        } else {
            std::cout << "Fail to create binary tree by inorder and lastorder" << std::endl;
        }
        break;
    default:
        break;
    }
};

int main()
{

#if 0
    /* 下面是一颗二叉树的三种遍历顺序 */
    std::vector<int> preorder = {1, 2, 4, 5, 8, 9, 3, 6, 7, 10};
    std::vector<int> inorder = {4, 2, 8, 5, 9, 1, 6, 3, 10, 7};
    std::vector<int> lastorder = {4, 8, 9, 5, 2, 6, 10, 7, 3, 1};
#endif

#if 0
#if 0
    BinaryTree *tree = new BinaryTree(preorder, inorder, 1);
#else
    BinaryTree *tree = new BinaryTree(inorder, lastorder, 2);
#endif
#endif

    /* 二叉搜索树 */
    BinarySearchTree *tree = new BinarySearchTree;
    std::vector<int> input_order = {5, 6, 3, 2, 4, 7, 10, 9, 8};
    for (auto input : input_order) {
        tree->insert_node(input);
    }

    tree->delete_node(5);
    tree->delete_node(2);
    tree->delete_node(3);
    tree->delete_node(4);
    tree->delete_node(6);
    tree->delete_node(10);

    tree->level_order();
    std::cout << std::endl;
    tree->pre_order(tree->get_root());
    std::cout << std::endl;
    tree->in_order(tree->get_root());
    std::cout << std::endl;
    tree->last_order(tree->get_root());
    std::cout << std::endl;

    delete tree;

    return 0;
}